home *** CD-ROM | disk | FTP | other *** search
/ C++ für Kids / C++ for kids.iso / SETUP / US / CBUILDER / DATA.Z / BITSET.H < prev    next >
C/C++ Source or Header  |  1997-02-13  |  18KB  |  629 lines
  1. #ifndef __STD_BITS
  2. #define __STD_BITS
  3. /* $Revision:   8.1  $ */
  4.  
  5. /***************************************************************************
  6.  *
  7.  * bitset - class bitset declaration
  8.  *
  9.  * $Id: bitset,v 1.55 1995/09/29 23:52:59 smithey Exp $
  10.  *
  11.  ***************************************************************************
  12.  *
  13.  * (c) Copyright 1994, 1995 Rogue Wave Software, Inc.
  14.  * ALL RIGHTS RESERVED
  15.  *
  16.  * The software and information contained herein are proprietary to, and
  17.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  18.  * intends to preserve as trade secrets such software and information.
  19.  * This software is furnished pursuant to a written license agreement and
  20.  * may be used, copied, transmitted, and stored only in accordance with
  21.  * the terms of such license and with the inclusion of the above copyright
  22.  * notice.  This software and information or any other copies thereof may
  23.  * not be provided or otherwise made available to any other person.
  24.  *
  25.  * Notwithstanding any other lease or license that may pertain to, or
  26.  * accompany the delivery of, this computer software and information, the
  27.  * rights of the Government regarding its use, reproduction and disclosure
  28.  * are as set forth in Section 52.227-19 of the FARS Computer
  29.  * Software-Restricted Rights clause.
  30.  *
  31.  * Use, duplication, or disclosure by the Government is subject to
  32.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  33.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  34.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  35.  * P.O. Box 2328, Corvallis, Oregon 97339.
  36.  *
  37.  * This computer software and information is distributed with "restricted
  38.  * rights."  Use, duplication or disclosure is subject to restrictions as
  39.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  40.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  41.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  42.  * then the "Alternate III" clause applies.
  43.  *
  44.  **************************************************************************/
  45.  
  46. #include <stdcomp.h>
  47. #include <stddefs.h>
  48.  
  49. #ifndef RWSTD_NO_NEW_HEADER
  50. #include <climits>
  51. #include <cstddef>
  52. #else
  53. #include <limits.h>
  54. #include <stddef.h>
  55. #endif
  56.  
  57. #ifdef RW_STD_IOSTREAM
  58. #include <iosfwd>
  59. #else
  60. class  ostream;
  61. class  istream;
  62. #endif
  63.  
  64. #ifndef RWSTD_NO_EXCEPTIONS
  65. #ifdef RW_STD_EXCEPT
  66. #include <stdexcept>
  67. #endif
  68. #endif
  69.  
  70. #include <string>
  71.  
  72. #ifndef RWSTD_NO_NAMESPACE
  73. namespace std {
  74. #endif
  75.  
  76. //
  77. // Exception error messages.
  78. //
  79. extern char RWSTDExport  __rw_bitset_InvalidPosition[];
  80. extern char RWSTDExport  __rw_bitset_InvalidCtorArgument[];
  81. extern char RWSTDExport  __rw_bitset_ConversionOverflow[];
  82.  
  83. template <size_t N>
  84. class  bitset
  85. {
  86.   private:
  87.     //
  88.     // The type of array in which we store the bits.
  89.     //
  90.     typedef unsigned int VectorType;
  91.     //
  92.     // Number of bits in an array element.
  93.     //
  94.     enum { BitsPerChunk = CHAR_BIT*sizeof(unsigned int) };
  95.     //
  96.     // Number of array elements.
  97.     //
  98. #ifndef RWSTD_BC5_ENUM_BUG
  99.     enum { NumOfElems = N == 0 ? 1 : 1 + ((N - 1) / BitsPerChunk) };
  100.     #define NELEMENTS NumOfElems
  101. #else
  102.     int NumOfElems () const
  103.     {
  104.         return N == 0 ? 1 : 1 + ((N - 1) / BitsPerChunk);
  105.     }
  106.     #define NELEMENTS NumOfElems()
  107. #endif /*RWSTD_BC5_ENUM_BUG*/
  108.     //
  109.     // Number of bits in an unsigned long.
  110.     //
  111.     enum { BitsInUnsignedLong = CHAR_BIT*sizeof(unsigned long) };
  112.     //
  113.     // The array of bits.
  114.     //
  115. #ifndef RWSTD_BC5_ENUM_BUG
  116.     VectorType bits[NELEMENTS];
  117. #else
  118.     VectorType* bits;
  119. #endif /*RWSTD_BC5_ENUM_BUG*/
  120.  
  121.   protected:
  122.     //
  123.     // Is pos a valid bitset position?
  124.     //
  125.     bool valid_position (size_t pos) const RWSTD_THROW_SPEC_NULL
  126.     {
  127.         return N > pos ? true : false;
  128.     }
  129.     //
  130.     // Given a bit position `pos', returns the index into the appropriate
  131.     // chunk in bits[] such that 0 <= index < BitsPerChunk.
  132.     //
  133.     size_t index (size_t pos) const RWSTD_THROW_SPEC_NULL
  134.     {
  135. #if UINT_MAX == 256
  136.         return 7 & pos;
  137. #elif UINT_MAX == 65535
  138.         return 15 & pos;
  139. #elif UINT_MAX == 4294967295
  140.         return 31 & pos;
  141. #elif UINT_MAX == 18446744073709551616
  142.         return 63 & pos;
  143. #else
  144.         return pos % BitsPerChunk;
  145. #endif
  146.     }
  147.  
  148.   public:
  149.     //
  150.     // bit reference
  151.     //
  152.     class reference
  153.     {
  154.         friend class bitset<N>;
  155.       private:
  156.         bitset<N>& ref;
  157.         size_t     pos;
  158.         reference (bitset<N>& r, size_t p) RWSTD_THROW_SPEC_NULL
  159.             : ref(r), pos(p) {}
  160.       public:
  161.         ~reference() RWSTD_THROW_SPEC_NULL {}
  162.         //
  163.         // for b[i] = x;
  164.         //
  165.         reference& operator= (bool val) RWSTD_THROW_SPEC_NULL
  166.         {
  167.             ref.set(pos, val); return *this;
  168.         }
  169.         //
  170.         // for b[i] = b[j];
  171.         //
  172.         reference& operator= (const reference& rhs) RWSTD_THROW_SPEC_NULL
  173.         {
  174.             ref.set(pos, rhs.ref.test(rhs.pos)); return *this;
  175.         }
  176.         //
  177.         // for x = ~b[i];
  178.         //
  179.         bool operator~ () const RWSTD_THROW_SPEC_NULL { return !ref.test(pos);}
  180.         //
  181.         // for x = b[i];
  182.         //
  183.         operator bool () const RWSTD_THROW_SPEC_NULL { return ref.test(pos); }
  184.         //
  185.         // flips the bit
  186.         //
  187.         reference& flip() RWSTD_THROW_SPEC_NULL { ref.flip(pos); return *this;}
  188.     };
  189.     //
  190.     // constructors
  191.     //
  192.     bitset () RWSTD_THROW_SPEC_NULL
  193.     {
  194. #ifndef RWSTD_BC5_ENUM_BUG
  195.         memset(bits, 0, sizeof(bits));
  196. #else
  197.         bits = new VectorType[NELEMENTS];
  198.         //
  199.         // TODO -- check for bits == 0 here?
  200.         //
  201.         memset(bits, 0, NELEMENTS*sizeof(VectorType));
  202. #endif /*RWSTD_BC5_ENUM_BUG*/
  203.     }
  204.     bitset (unsigned long val) RWSTD_THROW_SPEC_NULL
  205.     {
  206.         //
  207.         // Initialize first M bit positions to the corresponding
  208.         // bit values in val. M is the smaller of N and the value
  209.         // CHAR_BIT * sizeof(unsigned long).
  210.         //
  211. #ifndef RWSTD_BC5_ENUM_BUG
  212.         memset(bits, 0, sizeof(bits));
  213. #else
  214.         bits = new VectorType[NELEMENTS];
  215.         //
  216.         // TODO -- check for bits == 0 here?
  217.         //
  218.         memset(bits, 0, NELEMENTS*sizeof(VectorType));
  219. #endif /*RWSTD_BC5_ENUM_BUG*/
  220.         size_t M = N < BitsInUnsignedLong ? N : BitsInUnsignedLong;
  221.         for (size_t i = 0; i < M; i++)
  222.             if (val & (1 << i))
  223.                 set(i);
  224.     }
  225.     explicit bitset (const string& str,
  226.                      size_t pos = 0,
  227.                      size_t n = (size_t) -1)
  228.                      RWSTD_THROW_SPEC((out_of_range, invalid_argument));
  229.     //
  230.     // We explicitly defined the copy constructor, though
  231.     // WP 17.2.2.2 allows us to use the default generated one.
  232.     //
  233.     bitset (const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  234.     {
  235. #ifndef RWSTD_BC5_ENUM_BUG
  236.         memcpy(bits, rhs.bits, sizeof(bits));
  237. #else
  238.         bits = new VectorType[NELEMENTS];
  239.         //
  240.         // TODO -- check for bits == 0 here?
  241.         //
  242.         memcpy(bits, rhs.bits, NELEMENTS*sizeof(VectorType));
  243. #endif /*RWSTD_BC5_ENUM_BUG*/
  244.     }
  245.     //
  246.     // We explicitly defined the assignment, though
  247.     // WP 17.2.2.2 allows us to use the default generated one.
  248.     //
  249.     bitset<N>& operator= (const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  250.     {
  251.         if (!(this == &rhs))
  252. #ifndef RWSTD_BC5_ENUM_BUG
  253.             memcpy(bits, rhs.bits, sizeof(bits));
  254. #else
  255.             memcpy(bits, rhs.bits, NELEMENTS*sizeof(VectorType));
  256. #endif /*RWSTD_BC5_ENUM_BUG*/
  257.         return *this;
  258.     }
  259. #ifdef RWSTD_BC5_ENUM_BUG
  260.     ~bitset () RWSTD_THROW_SPEC_NULL { delete [] bits; }
  261. #endif
  262.     //
  263.     // bitset operations
  264.     //
  265.     bitset<N>& operator&= (const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  266.     {
  267.         for (size_t i = 0; i < NELEMENTS; i++)
  268.             bits[i] &= rhs.bits[i];
  269.         return *this;
  270.     }
  271.     bitset<N>& operator|= (const bitset<N>& rhs) RWSTD_THROW_SPEC_NULL
  272.     {
  273.